<?php

/**
 * 对比字符串数组，生成增减版本
 * @author 王文林 
 */
class diff
{
    /**
     * 对比字符串数组，生成增减版本
     * @param array $arr1
     * @param array $arr2
     * @return array 
     */
    static public function diffArray(array $arr1, array $arr2)
    {
        return diff::_diff_fn(diff::_diff_lsm($arr1, $arr2), $arr1, $arr2, count($arr1) - 1, count($arr2) - 1);
    }

    /**
     * 合并版本
     * @param array $arr
     * @param array $patch
     * @return array 
     */
    static public function patch($arr, $patch)
    {
        // delete phase
        for($i = count($patch) - 1; $i >= 0; $i--)
        {
            if($patch[$i][0] < 0)
            {
                array_splice($arr, $patch[$i][1], 1);
            }
        }

        // insert phase
        for($i = 0, $l = count($patch); $i < $l; $i++)
        {
            if($patch[$i][0] > 0)
            {
                array_splice($arr, $patch[$i][1], 0, array($patch[$i][2]));
            }
        }

        return $arr;
    }

    static private function _diff_lsm($a1, $a2)
    {
        $c = array();
        $l1 = count($a1);
        $l2 = count($a2);

        for($i = -1; $i < $l1; $i++)
        {
            $c[$i] = array();
            for($j = -1; $j < $l2; $j++)
            {
                $c[$i][$j] = 0;
            }
        }

        for($i = 0; $i < $l1; $i++)
        {
            for($j = 0; $j < $l2; $j++)
            {
                if($a1[$i] == $a2[$j])
                {
                    $c[$i][$j] = $c[$i - 1][$j - 1] + 1;
                }
                else
                {
                    $c[$i][$j] = max($c[$i][$j - 1], $c[$i - 1][$j]);
                }
            }
        }

        return $c;
    }

    static private function _diff_fn($c, $a1, $a2, $i, $j)
    {
        if($i >= 0 && $j >= 0 && $a1[$i] == $a2[$j])
        {
            $diff = diff::_diff_fn($c, $a1, $a2, $i - 1, $j - 1);
        }
        else
        {
            if($j >= 0 && ($i == -1 || $c[$i][$j - 1] >= $c[$i - 1][$j]))
            {
                $diff = diff::_diff_fn($c, $a1, $a2, $i, $j - 1);
                $diff[] = array(1, $j, $a2[$j]);
            }
            else if($i >= 0 && ($j == -1 || $c[$i][$j - 1] < $c[$i - 1][$j]))
            {
                $diff = diff::_diff_fn($c, $a1, $a2, $i - 1, $j);
                $diff[] = array(-1, $i, $a1[$i]);
            }
            else
            {
                $diff = array();
            }
        }

        return $diff;
    }

}

?>
